# -*- coding: utf-8 -*-

from django.conf import settings

import math
import logging

logger=logging.getLogger('__name__')

class BiCluster:

    def __init__(self,vec,left=None,right=None,distance=0.0,clusterid=None,category=None):
        self.left=left
        self.right=right
        self.vec=vec
        self.clusterid=clusterid
        self.distance=distance
        self.category=category

    def printclust(self, clust, labels=None, n=0, depthlimit=10):
        # indent to make a hierarchy layout
        for i in range(n if n<depthlimit else depthlimit ): 
            print ' ',
        if clust.clusterid<0:
            # negative id means that this is branch
            print str(clust.category)+'- distance:' + str(clust.distance)
        elif clust.distance < 1.0:
            # positive id means that this is an endpoint
            if labels==None: 
                print clust.clusterid
            else:
                print clust.clusterid, labels[clust.clusterid]

        # now print the right and left branches
        if clust.left!=None: self.printclust(clust.left,labels=labels,n=n+1)
        if clust.right!=None: self.printclust(clust.right,labels=labels,n=n+1)
  
def parse_cluster(clust, clust_list, distance_threshold):
        member_set = set()
        add_cluster_memebers(clust, member_set)
        clust_list.append(member_set)

def add_cluster_memebers(clust, member_set):
    if clust.clusterid<0:
        add_cluster_memebers(clust.left, member_set)
        add_cluster_memebers(clust.right, member_set)
    else:
        member_set.add(clust.clusterid)

class NewsClusterer:

    def __init__(self):
        self.hcluster_threshold = settings.NEWS_CLUSTERER_PARAMS['distance_threshold']
        self.cluster_num_limit = settings.NEWS_CLUSTERER_PARAMS['cluster_num_limit']

    def cluster(self, data_list):
        #文本数量
        vector_size = len(data_list)
        logger.debug('vector_size:'+' '+str(vector_size))
    
        id_list = [i for i in xrange(0, vector_size, 1)]
        vectors = self.__build_cluster_vectors(data_list, vector_size)
    
        clusters = self.__hcluster(vectors, id_list, cosine_simlarity)
    
        clust_list = []
        for cluster in clusters:
            parse_cluster(cluster, clust_list, self.hcluster_threshold)

        # sorts the clusters according to the doc count of each cluster
        sorted_clust_list = sorted(clust_list, key=lambda x: len(x), reverse=True)

        return sorted_clust_list[0:self.cluster_num_limit]

    def __build_cluster_vectors(self, data_list, vector_size):
        key_list, data_dim = self.__build_occurrance_list(data_list)
        vectors = []
        for row_data in key_list:
            vectors.append(self.__init_data_row(row_data, data_dim))

        return vectors

    def __build_occurrance_list(self, data_list):
        keywords_map = {}
        key_list = []
        keyword_id = 0
        for keywords in data_list:
            occ_set = set()
            for keyword in keywords:
                if keywords_map.has_key(keyword):
                    occ_set.add(keywords_map[keyword])
                else:
                    keywords_map[keyword] = keyword_id
                    occ_set.add(keyword_id)
                    keyword_id += 1
            #默认一个文档里面的关键词只能出现一次
            key_list.append(occ_set)
    
        return key_list, len(keywords_map)

    def __init_data_row(self, element_list, data_dim):
        keywords_dict = {}
        for idx in element_list:
            keywords_dict[idx] = 1

        return keywords_dict
    
    def __hcluster(self, data_vec_list, data_id_list, distance):
        distances = {}
        currentclustid = -1

        # Clusters are initially just the rows
        data_size = len(data_vec_list)
        clust=[BiCluster(data_vec_list[i], clusterid=data_id_list[i]) for i in xrange(data_size)]

        clust_size = len(clust)
        while clust_size > 1:
            lowestpair = (0,1)
            closest = 1 - distance(clust[0].vec,clust[1].vec)

            clust_size = len(clust)
            # loop through every pair looking for the smallest distance
            for i in xrange(clust_size - 1):
                cluster_id_i = clust[i].clusterid
                for j in xrange(i + 1, clust_size):
                # distances is the cache of distance calculations
                    cluster_id_j = clust[j].clusterid
                    if (cluster_id_i, cluster_id_j) in distances:
                        d =  distances[(cluster_id_i, cluster_id_j)]
                    elif (cluster_id_j, cluster_id_i) in distances:
                        d =  distances[(cluster_id_j, cluster_id_i)]
                    else:
                        d = distances[(cluster_id_i, cluster_id_j)] = 1 - distance(clust[i].vec,clust[j].vec)

                    if d < closest:
                        closest=d
                        lowestpair=(i,j)

            if closest > self.hcluster_threshold:
                break
            # calculate the average of the two clusters
            mergevec = self.__build_merge_vec(clust[lowestpair[0]].vec, clust[lowestpair[1]].vec)

            # create the new cluster
            newcluster = BiCluster(mergevec,left=clust[lowestpair[0]],
                                    right=clust[lowestpair[1]],
                                    distance=closest,clusterid =currentclustid)

            # cluster ids that weren't in the original set are negative
            currentclustid -= 1
            del clust[lowestpair[1]]
            del clust[lowestpair[0]]
            clust.append(newcluster)

        return clust
 
    
    def __build_merge_vec(self, vec_1, vec_2):
        # vec_1, vec_2是dict类型储存的稀疏矩阵
        new_vec = dict()
        for element in vec_1:
            new_vec[element] = float(vec_1[element]) / 2

        for element in vec_2:
            if element in new_vec:
                new_vec[element] += float(vec_2[element]) / 2
            else:
                new_vec[element] = float(vec_2[element]) / 2

        return new_vec

def cosine_simlarity(vec_1, vec_2):
    # vec_1, vec_2是dict类型储存的稀疏矩阵
    sum_v1_v2 = 0.0
    for element in vec_1:
        if element in vec_2:
            sum_v1_v2 += vec_1[element] * vec_2[element]

    if sum_v1_v2 == 0.0:
        return 0

    sqrt_v1 = sqrt_v2 = 0.0
    for element in vec_1:
        sqrt_v1 += vec_1[element] ** 2
    sqrt_v1 = math.sqrt(sqrt_v1)

    for element in vec_2:
        sqrt_v2 += vec_2[element] ** 2
    sqrt_v2 = math.sqrt(sqrt_v2)

    if sqrt_v1 == 0.0 or sqrt_v2 == 0.0:
        return 0
  
    return sum_v1_v2 / (sqrt_v1 * sqrt_v2)

